package chapter01;

public class IsValidSudoku {
    //暴力
    /**
     * 1)判断一行是否有重复数字 为了节省时间 只在第一次进入每一行进行判断
     * 2)判断一列是否有重复数字 为了节省时间 只在第一次进入每一列进行判断
     * 3)判断3x3方格是否有重复数字 i%3==0&&j%3==0
     * 4)遍历重复数字 用count[i]表示数字i的出现次数  时间复杂度达到O(n)
     */
    public boolean isValidSudoku(char[][] board) {
        int length=board.length;
        for(int row=0;row<length;row++){
            if(!row(board,row,length)){
                return false;
            }
            for(int col=0;col<length;col++){
                if(row==0){
                    if(!col(board,col,length)){
                        return false;
                    }
                }
                if(row%3==0&&col%3==0){
                    if(!soild(board,row,col)){
                        return false;
                    }
                }
            }
        }
        return true;
    }

    public boolean row(char[][] board,int row,int length){
        int[] count=new int[10];
        for(int j=0;j<length;j++){
            if (board[row][j] >= '0' && board[row][j] <= '9') {
                count[board[row][j]-'0']++;
                if(count[board[row][j]-'0']>1){
                    return false;
                }
            }
        }
        return true;
    }

    public boolean col(char[][] board,int col,int length){
        int[] count=new int[10];
        for(int j=0;j<length;j++){
            if (board[j][col] >= '0' && board[j][col] <= '9') {
                count[board[j][col]-'0']++;
                if(count[board[j][col]-'0']>1){
                    return false;
                }
            }
        }
        return true;
    }

    public boolean soild(char[][] board,int row,int col){
        int[] count=new int[10];
        for(int i=row;i<row+3;i++){
            for(int j=col;j<col+3;j++){
                if (board[i][j] >= '0' && board[i][j] <= '9') {
                    count[board[i][j]-'0']++;
                    if(count[board[i][j]-'0']>1){
                        return false;
                    }
                }
            }
        }
        return true;
    }
}
